package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offer34 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        final Solution solution = new Solution();
        List<List<Integer>> temp = new ArrayList<>();
        temp = solution.pathSum(node1, 13);
        System.out.println(temp);
    }

     //Definition for a binary tree node.
     static class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
    static class Solution {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return ans;
        }

        public void dfs(TreeNode root, int target){
            if(root == null){
                return;
            }
            target -= root.val;
            list.add(root.val);
            if(root.left == null && root.right == null && target == 0){
                ans.add(new ArrayList<>(list));
                return;
            }
            if(root.left != null){
                dfs(root.left,target);
//                target += root.val;
                list.removeLast();
            }
            if(root.right != null){
                dfs(root.right,target);
//                target += root.val;
                list.removeLast();
            }
        }
    }
}
